Field of the Invention
This invention relates to systems and methods for implementing a low-density parity check (LDPC) decoding algorithm.
Background of the Invention
A. LDPC Codes and Min-Sum Decoding
Low-density parity-check (LDPC) codes were discovered by Gallager in 1962, and rediscovered and shown to be Shannon-limit approaching in the late 1990's. These codes, decoded with iterative decoding based on belief propagation, such as the sum-product algorithm (SPA), achieve near-capacity error performance [1].
Quasi-cyclic (QC) LDPC codes are a special class of the LDPC codes with structured H matrix which can be generated by the expansion of a mb×nb base matrix. Each 1's element in the base matrix can be expanded by a circularly right-shifted b×b identity sub-matrix. QC-LDPC codes have advantages over other types of LDPC codes in hardware implementations of both encoding and decoding. Encoding of a QC-LDPC code can be efficiently implemented using simple shift registers. In hardware implementation of a QC-LDPC decoder, the QC structure of the code simplifies the wire routing for message passing.
Richardson and Urbanke [2] showed there exists near-triangular sub-matrix HP in sparse matrix H=[HI, HP], such that
                              H          P                =                  [                                                    B                                            T                                                                    D                                            E                                              ]                                    (        1        )            
where HP is an m×m matrix and retains the rank of H, and T is lower-triangular matrix whose dimension t is close to the full dimension m. An efficient encoding algorithm was derived exploiting the sparseness of HI (the identity matrix) and back-substitution over the lower-triangular matrix T. Myung, et al. [3] presented a special class of QC-LDPC codes which exhibit special near-lower-triangular QC H sub-matrix (i.e., H contains a lower triangular QC sub-matrix T whose dimension is near to m) and developed an efficient encoding algorithm which further incorporates the QC property into the back-substitution approach in [2]. For the practical LDPC coding system implementations, it has been well recognized that the conventional code-to-encoder/decoder design approach, i.e., first construct the code and then develop the encoder/decoder hardware implementations, is not the most efficient and a better solution is to jointly consider the code construction and encoder/decoder hardware implementation. This is referred to as joint LDPC coding system design. Zhong and Zhang [4] proposed a joint design of block-LDPC codes subject to certain hardware-oriented constraints that ensure the effective encoder and decoder hardware implementations. Consequently, the constructed codes enable a pipelined partially parallel block-LDPC encoder, following the methodology of [2], and a partially parallel block-LDPC decoder.
Li, et al. [5] showed the existence of QC generator matrix, denoted by G, for most QC-LDPC codes, and thus encoding may be carried out by multiplying an input data with the systematic QC G matrix. Xiang, et al. [6] presented an improved all-purpose multi-rate iterative decoder architecture for QC-LDPC codes, which implements the normalized min-sum algorithm, rearranges the original two-phase message-passing flow, and adopts an efficient quantization method for the second minimum absolute values, an optimized storing scheme for the position indexes and signs, and an elaborate clock gating technique for substantive memories and registers.
The systems and methods disclosed herein provide an improved approach for performing LDPC decoding using Tanner graphs.